package TwoSeach;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: TwoSeach
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-11-04  17:06
 * @Description: TODO
 * @Version: 1.0
 */
public class 寻找两个正序数组的中位数4 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 将nums2 设置成为最大长度那个数组
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length;
        int n = nums2.length;

        // 分割线左边所有的元素满足的个数m+(n-m+1)/2
        int totalleft = (m + n + 1) / 2;

        // 在nums1[0,m] 中查找到恰当的分割线
        // 使得nums[i-1]<=nums2[j] &&nums2[j-1]<=nums1[i]
        int left = 0;
        int right = m;
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalleft - i;
            if (nums1[i - 1] > nums2[j]) {
                // [left，i-1]
                right = i - 1;
            } else {
                // [i，right]
                left = i;
            }
        }
        int i = left;
        int j = totalleft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        if ((m + n) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }
    }
}
